maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]


def print_path(Close):  # 打印最短路径
    path = []
    tmp = Close[-1]
    while tmp[3] != -1:
        path.append(Close[tmp[3]][0:2])
        tmp = Close[tmp[3]]
    path.reverse()
    print(f'BFS 得最短路径如下: ')
    for i in path:
        print(f'{i} → ', end='')
    print(f'{(Close[-1][0], Close[-1][1])}')
    print(f'长度为 {len(path)}, 总试探步数 {len(Close) - 1}')


def BFS(x0, y0, x1, y1):  # 起点(x0,y0) 终点(x1,y1)
    visited = [(x0, y0)]  # 检验某点是否走过
    Close = [(x0, y0, 0, -1)]
    Open = [(x0, y0, 0, -1)]
    # Close、Open中的节点信息是四元组: (横坐标、纵坐标、当前节点在Close中的下标、父节点在Close中的下标
    while Open:
        cur = Open.pop(0)
        for dir in dirs:  # 向四个方向尝试
            tmp = (cur[0] + dir[0], cur[1] + dir[1], len(Close), cur[2])
            # 下一步是否可走(不是边界、障碍且未被访问)
            if 0 < tmp[0] < 9 and 0 < tmp[1] < 9 and (tmp[0], tmp[1]) not in visited and maze[tmp[0]][tmp[1]] == 0:
                visited.append((tmp[0], tmp[1]))  # 相邻可走方块标记为已访问,加入Close 与 Open中
                Close.append(tmp)
                Open.append(tmp)
                if (tmp[0], tmp[1]) == (x1, y1):  # 如果找到终点，直接得到最短路径
                    print_path(Close)  # 输出路径并结束 bfs
                    return


BFS(1, 1, 8, 8)